Hondarraren teorema txinatarra kongruentzien ekuazio sistemak ebazteko balio duen teorema da. Teorema hau aplikatzeko baldintza bakarra ondokoa da: ekuazioen moduluak beraien artean lehenak izan behar dira, hau da,
izan behar da m ekuazio sistemetako edozein ekuazioaren modulua izanik.
Hondarraren teorema txinatarrak zera dio: demagun kongruentzia sistema bat dugula eta bertako ekuazio guztien moduluak beraien artean lehenak direla. Orduak sistemak soluzio bakarra izango du
moduluarekiko. Existitzen diren beste soluzio guztiak
motakoak izango dira.
Kongruentzia sistema bat:
(mod
)
(mod
)
(mod
)
non
den
denean
Izan bitez
modulu guztien biderkadura eta
ez diren moduluen biderkadura. Hipotesiagatik badakigu
denean, beraz,
da. Ondorioz,
(mod
)-k soluzio bat du eta bakarra da
moduluarekiko. Soluzio horri
deituko diogu.
sistema osoaren soluzioa izango da. Soluzioa dela ikustekoa
(mod
) betetzen dela ikusiko dugu.
bakoitza
-gatik zatigarria da
izan ezik. Beraz
(mod
).
-k
(mod
) betetzen duenez
(mod
). Beraz,
soluzioa da.
moduluarekiko bakarra dela ziurtatzeko, x eta y, bi soluzio hartuko dutugu. Bi horiek soluzioak badira
(mod
) eta
(mod
)
guztietarako. Beraz,
(mod
)
guztietarako. Moduluak elkarrekiko lehenak direnez
(mod
) dugu. Orduan, badakigu sistemaren soluzio guztiak kongruenteak direla
moduluarekiko.
Lehen esan bazala, kongruentzia linealetako sistemak ebazteko balio du teorema honek. Ebatzi dezagun, bat hondarraren teorema txinatarra nola aplikatzen den ikusteko. Demagun, hondako kongruentzia sistema dugula:
Lehenik eta behin kalkulatu dezagun
.
Ondoren kalkulatu desagua modulu bakoitza, oro har,
.
Has gaitezen kongruentzia lineal bakoitza bere aldetik aztertzen:
1.kasua
Bezouten identitatea erabiliz:
Beraz,
2.kasua
Bezouten identitatea erabiliz:
Beraz,
3.kasua
Bezouten identitatea erabiliz:
Beraz,
Teoremaren frogan erabili dugun notazioarekin,
. Horiekin soluzio bat idatziko dugu:
Sistemaren soluzio guztiak
edozein izanik
Hondarraren txinatar teorema Gödelen segiden zenbaketarako erabiltzen da, Gödel-en osatugabetasunaren teoremak frogatzeko erabili zenean.
Faktore lehenaren FTT algoritmoak hondarraren teorema txinatarra erabiltzen du
tamainuko Fourier-en transformatu azkarraren zenbaketa txikitzeko
tamainuko zenbaketa batera,
eta
elkarrekiko lehenak direla zihurtatuz.
RSAren algoritmo gehienek hondarraren teorema txinatarra erabiltzen dute HTTPS ziurtagiriak sinatzeko eta deszifratzeko.
Hondarraren teorema txinatarra mezu ezkutuak bidaltzeko ere erabil daiteke. Pertsona talde batean mezu batzuk partekatzean datza. Denek batera bidalitako mezu horietatik mezu sekretua lor dezakete. Mezu horietako bakoitza kongruentzia bat da, eta kongruentzia sistema ebaztean hondarraren teorema txinatarra erabiliz, mezu sekretua lortzen da.